{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Moves to Equal Array Elements II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMoves2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小操作次数使数组元素相等 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，返回使所有数组元素相等需要的最小操作数。</p>\n",
    "\n",
    "<p>在一次操作中，你可以使数组中的一个元素加 <code>1</code> 或者减 <code>1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "只需要两次操作（每次操作指南使一个元素加 1 或减 1）：\n",
    "[<strong><em>1</em></strong>,2,3]  =&gt;  [2,2,<strong><em>3</em></strong>]  =&gt;  [2,2,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,10,2,9]\n",
    "<strong>输出：</strong>16\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-moves-to-equal-array-elements-ii](https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-moves-to-equal-array-elements-ii](https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[1,10,2,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i in nums:\n",
    "            count+=abs(i-nums[len(nums)//2])\n",
    "\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        mid = len(nums) // 2\n",
    "\n",
    "        result = 0\n",
    "\n",
    "# 每个数和中位数的差的和\n",
    "\n",
    "        for j in nums:\n",
    "\n",
    "            result += abs(j-nums[mid])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mid = len(nums) // 2\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans += abs(nums[i] - nums[mid])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        aver = nums[n >> 1]\n",
    "        return sum(abs(i - aver) for i in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        aver = nums[n >> 1]\n",
    "        return sum(abs(i - aver) for i in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        medium_num = self.KthNumber(nums, n//2)\n",
    "        print(medium_num)\n",
    "        move = 0\n",
    "        for num in nums:\n",
    "            move += abs(num-medium_num)\n",
    "        return move\n",
    "\n",
    "\n",
    "    def KthNumber(self, nums, k):\n",
    "        def partion(l, r):\n",
    "            if l>=r:\n",
    "                return l\n",
    "            i, j = l, r\n",
    "            dummy = nums[l]\n",
    "            while i<j:\n",
    "                while i<j and nums[j] >= dummy:\n",
    "                    j -= 1\n",
    "                nums[i] = nums[j]\n",
    "                while i<j and nums[i] < dummy:\n",
    "                    i += 1\n",
    "                nums[j] = nums[i]\n",
    "            nums[i] = dummy\n",
    "            return i\n",
    "        \n",
    "        l, r = 0, len(nums)-1\n",
    "        while l<r:\n",
    "            mid = partion(l, r)\n",
    "            if mid == k:\n",
    "                break\n",
    "            elif mid < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return nums[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        nums.sort()\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<j:\n",
    "            cnt+=nums[j]-nums[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=nums[len(nums)//2]\n",
    "        return sum([abs(x-n) for x in nums])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        temp1 = int(statistics.median(nums))\n",
    "        print(help(median))\n",
    "        temp2 = temp1 + 1\n",
    "        ans1 = 0\n",
    "        ans2 = 0\n",
    "        for num in nums:\n",
    "            ans1 += abs(num - temp1)\n",
    "            ans2 += abs(num - temp2)\n",
    "\n",
    "        return min(ans1, ans2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        heap = [i for i in nums]\n",
    "        heapq.heapify(heap)\n",
    "        mid = heap[0]\n",
    "        for _ in range(len(heap)//2+1):\n",
    "            mid = heapq.heappop(heap)\n",
    "        return sum([abs(i-mid) for i in nums])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        a = [0] * l\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                continue\n",
    "            else:\n",
    "                a[i] = (a[i-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * l\n",
    "        ans = inf\n",
    "        for i in range(l-2, -1, -1):\n",
    "            before = l - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "            ans = min(ans, b[i] + a[i])\n",
    "\n",
    "        # ans = inf\n",
    "        # for i in range(l):\n",
    "        #     ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums = [x - nums[0] for x in nums]\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # print(nums)\n",
    "        # print(s)\n",
    "        n = len(nums)\n",
    "        return s[n] - s[n//2] * 2 - nums[n//2] * (n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                a.append(0)\n",
    "            else:\n",
    "                a.append(a[-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * len(nums)\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            before = len(nums) - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        a = [0] * l\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                continue\n",
    "            else:\n",
    "                a[i] = (a[i-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * l\n",
    "        for i in range(l-2, -1, -1):\n",
    "            before = l - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(l):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                a.append(0)\n",
    "            else:\n",
    "                a.append(a[-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * len(nums)\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            before = len(nums) - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        dp1 = [0]*n\n",
    "        dp2 = [0]*n\n",
    "\n",
    "        i = 0\n",
    "        cur = 0\n",
    "        while i < n-1:\n",
    "            while nums[i] == nums[i+1] and (i < n-1-1):\n",
    "                i += 1\n",
    "                dp1[i] = cur\n",
    "            change = (nums[i+1] - nums[i]) * (i+1)\n",
    "            cur += change\n",
    "            i+=1\n",
    "            dp1[i] = cur\n",
    "\n",
    "        i = n-1\n",
    "        cur = 0\n",
    "        while i > 0:\n",
    "            while nums[i] == nums[i-1] and (i > 0+1):\n",
    "                i -= 1\n",
    "                dp2[i] = cur\n",
    "            change = (nums[i] - nums[i-1]) * (n-i)\n",
    "            cur += change\n",
    "            i -= 1\n",
    "            dp2[i] = cur\n",
    "            \n",
    "        return(min([dp1[i]+dp2[i] for i in range(len(dp1))]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        k = (len(nums)+1)//2\n",
    "        left=[]\n",
    "        right=[]\n",
    "        \n",
    "        def quickselect(curnums,k)->int:\n",
    "            if len(curnums)==1:\n",
    "                return curnums[0]\n",
    "            nonlocal right\n",
    "            nonlocal left\n",
    "            pivot = random.sample(curnums,1)[0]\n",
    "            #print(pivot)\n",
    "            curleft=[]\n",
    "            curright=[]\n",
    "            curmid=[]\n",
    "            for x in curnums:\n",
    "                if x<pivot:\n",
    "                    curleft.append(x)\n",
    "                elif x==pivot:\n",
    "                    curmid.append(x)\n",
    "                else:\n",
    "                    curright.append(x)\n",
    "            r = len(curmid)+len(curleft)\n",
    "            print(k,len(curleft),r)\n",
    "            print(curleft,curmid, curright)\n",
    "            if len(curleft)>=k:\n",
    "                right+=curmid+curright\n",
    "                res = quickselect(curleft,k)\n",
    "            elif r<k:\n",
    "                left+=curmid+curleft\n",
    "                res = quickselect(curright,k-r)\n",
    "            else:\n",
    "                right+=curright\n",
    "                left+=curleft\n",
    "                res=pivot\n",
    "            \n",
    "            return res\n",
    "            \n",
    "        pivot = quickselect(nums,k)\n",
    "        print(pivot,left,right)\n",
    "        return pivot*(len(left))-sum(left)+sum(right)-pivot*(len(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        elif(n == 2):\n",
    "            return abs(nums[0] - nums[1])\n",
    "        \n",
    "        temp = nums.copy()\n",
    "        temp.sort()\n",
    "\n",
    "        b1 = [0] * n\n",
    "        b2 = [0] * n\n",
    "        b = [0] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            b1[i] = b1[i-1] + (temp[i] - temp[i-1]) * i\n",
    "        for i in range(1, n):\n",
    "            b2[n-1-i] = b2[n-i] + (temp[n-i] - temp[n-1-i]) * i\n",
    "        \n",
    "        for i in range(n):\n",
    "            b[i] = b1[i] + b2[i]\n",
    "        \n",
    "        return min(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e, numbers):\n",
    "            idx = randint(s, e)\n",
    "            numbers[s], numbers[idx] = numbers[idx], numbers[s]\n",
    "\n",
    "            pivot = numbers[s]\n",
    "            l, r = s + 1, e\n",
    "\n",
    "            while l < r:\n",
    "                while numbers[l] <= pivot and l < r:\n",
    "                    l += 1\n",
    "                while numbers[r] > pivot and l < r:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    numbers[l], numbers[r] = numbers[r], numbers[l]\n",
    "                \n",
    "            if numbers[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            numbers[s], numbers[r] = numbers[r], numbers[s]\n",
    "\n",
    "            return r\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        def find_median(start, end, numbers, target_idx):\n",
    "            p_id = partition(start, end, numbers)\n",
    "\n",
    "            if p_id == target_idx:\n",
    "                return numbers[p_id]\n",
    "            elif p_id < target_idx:\n",
    "                return find_median(p_id + 1, end, numbers, target_idx)\n",
    "            else:\n",
    "                return find_median(start, p_id - 1, numbers, target_idx)\n",
    "\n",
    "        median = find_median(0, len(nums)-1, nums, len(nums)//2)\n",
    "        return sum(abs(n - median) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(nums, s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while nums[l] <= pivot and l < r:\n",
    "                    l += 1\n",
    "                while nums[r] >= pivot and l < r:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "            return r\n",
    "\n",
    "        def find_median(nums, s, e, target):\n",
    "            idx = partition(nums, s, e)\n",
    "\n",
    "            if idx < target:\n",
    "                return find_median(nums, idx+1, e, target)\n",
    "            elif idx > target:\n",
    "                return find_median(nums, s, idx-1, target)\n",
    "\n",
    "            return nums[idx]\n",
    "            \n",
    "\n",
    "        median = find_median(nums, 0, len(nums)-1, len(nums)//2)\n",
    "\n",
    "        return sum(abs(n-median) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while l < r and nums[l] <= pivot:\n",
    "                    l += 1\n",
    "                while l < r and nums[r] > pivot:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "\n",
    "            return r\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def find_median(start, end, target_idx):\n",
    "            idx = partition(start, end)\n",
    "\n",
    "            if idx < target_idx:\n",
    "                return find_median(idx+1, end, target_idx)\n",
    "            elif idx > target_idx:\n",
    "                return find_median(start,idx - 1, target_idx)\n",
    "\n",
    "            return nums[idx]\n",
    "        \n",
    "        median = find_median(0, len(nums)-1, len(nums) // 2)\n",
    "\n",
    "        return sum(abs(n - median) for n in nums)\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Quick Select: O(n+lgn),O(n)\n",
    "#median minimize l1 loss (sum of abs(y-x_i))\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def pivot(l,r):\n",
    "            p=nums[r]\n",
    "            j=l\n",
    "            for i in range(l,r):\n",
    "                if nums[i]<=p: #swap what's smaller to the front, maintaining a frontier j\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "                    j+=1\n",
    "            nums[r],nums[j]=nums[j],nums[r]\n",
    "            return j\n",
    "        \n",
    "        def randPivot(l,r):\n",
    "            i=random.randint(l,r)\n",
    "            nums[r],nums[i]=nums[i],nums[r]\n",
    "            return pivot(l,r)\n",
    "\n",
    "\n",
    "        def quickSelect(k,l,r): #find the kth smallest\n",
    "            if l>=r: return nums[l]\n",
    "            j=randPivot(l,r)\n",
    "            if j==k: return nums[k]\n",
    "            elif j>k: return quickSelect(k,l,j-1)\n",
    "            elif j<k: return quickSelect(k,j+1,r)\n",
    "\n",
    "        t=quickSelect(n//2,0,n-1)\n",
    "        return sum([abs(t-x) for x in nums])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while l < r and nums[l] <= pivot:\n",
    "                    l += 1\n",
    "                while l < r and nums[r] > pivot:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "\n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "\n",
    "            return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def find_median(s, e, target_idx):\n",
    "            pivot_idx = partition(s, e)\n",
    "            \n",
    "            if pivot_idx < target_idx:\n",
    "                return find_median(pivot_idx + 1, e, target_idx)\n",
    "            elif pivot_idx > target_idx:\n",
    "                return find_median(s, pivot_idx - 1, target_idx)\n",
    "            \n",
    "            return nums[pivot_idx]\n",
    "\n",
    "        median = find_median(0, len(nums)-1, len(nums) // 2)\n",
    "\n",
    "        return sum(abs(median - n) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minMoves2(self, nums: List[int]) -> int:\n",
    "        # # 找中位数\n",
    "        # nums.sort()\n",
    "        # return sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    def partition(self, nums, l, r):\n",
    "        i = random.randint(l, r)\n",
    "        nums[i], nums[r] = nums[r], nums[i]\n",
    "        pivt = nums[r]\n",
    "        i = l\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivt:#这里的到一定是小于等于的\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                i += 1\n",
    "        nums[i], nums[r] = nums[r], nums[i]\n",
    "        return i\n",
    "    #关键是快速选择的主程序是啥呢，这个是比较关键的\n",
    "    def quickselect(self, nums, l, r, k):\n",
    "        idx = self.partition(nums, l, r)\n",
    "        if idx == k:\n",
    "            return idx\n",
    "        if k < idx:\n",
    "            return self.quickselect(nums, l, idx - 1, k)\n",
    "        return self.quickselect(nums, idx+1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        helper = Helper()\n",
    "        idx = helper.quickselect(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            ans += abs(n - nums[idx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        x = self.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)\n",
    "\n",
    "    def randomPartition(self, nums, l, r):\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return self.partition(nums, l, r)\n",
    "\n",
    "    def partition(self, nums, l, r):\n",
    "        povit = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] < povit:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1],nums[r] = nums[r], nums[i+1]\n",
    "        return i + 1\n",
    "    \n",
    "    def quickSelected(self, nums, l, r, k):\n",
    "        index = self.randomPartition(nums, l, r)\n",
    "        if index == k:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return self.quickSelected(nums, l, index - 1, k )\n",
    "        return self.quickSelected(nums, index + 1, r, k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def quick_select(nums, L, R, k):\n",
    "    \"\"\"快速选择, 返回 nums 中第 k 大的数 (k 从 0 开始).\"\"\"\n",
    "    t = randint(L, R)\n",
    "    nums[t], nums[R] = nums[R], nums[t]\n",
    "    left, idx = L - 1, L\n",
    "    while idx < R:\n",
    "        if nums[idx] > nums[R]:\n",
    "            left += 1\n",
    "            nums[left], nums[idx] = nums[idx], nums[left]\n",
    "        idx += 1\n",
    "    left += 1\n",
    "    nums[left], nums[R] = nums[R], nums[left]\n",
    "    if left == k:\n",
    "        return nums[left]\n",
    "    elif left > k:\n",
    "        return quick_select(nums, L, left - 1, k)\n",
    "    elif left < k:\n",
    "        return quick_select(nums, left + 1, R, k)\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mid = quick_select(nums,0,n-1,n//2)\n",
    "        ans = 0\n",
    "        for i ,v in enumerate(nums):\n",
    "            ans += abs(v-mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        def quick_sort(arr, l, r, k):\n",
    "            if l >= r: return arr[k]\n",
    "            i, j = l, r\n",
    "            random_index = random.randint(l, r)\n",
    "            arr[l], arr[random_index] = arr[random_index], arr[l]\n",
    "            pivot = arr[l]\n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= pivot: j -= 1\n",
    "                arr[i] = arr[j]\n",
    "                while i < j and arr[i] <= pivot: i += 1\n",
    "                arr[j] = arr[i]\n",
    "            arr[i] = pivot\n",
    "            if k < i: return quick_sort(arr, l, i - 1, k) \n",
    "            if k > i: return quick_sort(arr, i + 1, r, k)\n",
    "            return arr[k] #第k + 1小的数\n",
    "        n = len(nums)\n",
    "        mid = quick_sort(nums, 0, n - 1, n // 2)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += abs(num - mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        #每次增加或减少array中的一个元素\n",
    "        #最终所有的值全部都相同，相当于就是变成median啊\n",
    "        #O(N)内找到median\n",
    "        #有没有更好的方案？\n",
    "        #毕竟只需要返回一个数字，而不真的需要median\n",
    "        #每次只能修改一个元素\n",
    "        #一定是大家移动到median而不是大家一起抵达average。因为median两侧元素个数相同，这样相当于贪心地每次都是移动较少的元素\n",
    "        #修改partition算法，使得其可以在一次操作中就返回结果\n",
    "        #每次操作都是返回，将当前子序列修改到和第k个元素相同的成本\n",
    "        #在partition过程中，统计其移动的结果。其中数组和并不改变\n",
    "        #lessSum+largerSum+ (j-i)*pivot就是总的结果\n",
    "\n",
    "        def partition(nums,start,end,pivot):    #按照pivot执行\n",
    "            if start+1==end:\n",
    "                return 0,1,0,0      #严格小于，小于等于，小于的差值总和，大于的差值总和\n",
    "            i,j,k=start,start,end-1\n",
    "            lessSum=0\n",
    "            largerSum=0\n",
    "            while j<=k:\n",
    "                if nums[j]<pivot:\n",
    "                    lessSum+=pivot-nums[j]\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                elif nums[j]>pivot:\n",
    "                    largerSum+=nums[j]-pivot\n",
    "                    nums[j],nums[k]=nums[k],nums[j]\n",
    "                    k-=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            \n",
    "            return i-start,j-start,lessSum,largerSum      #小于，小于等于\n",
    "        \n",
    "        #将数组中所有的元素都变为第k大的元素的成本，返回值是第k个元素，以及变成其的成本。\n",
    "\n",
    "        def serachKth(nums,start,end,k):        #在start,end中搜索第k个元素。pivot可以取middle的\n",
    "            pivot=nums[start]\n",
    "            less,lessOrEqual,lessSum,largerSum=partition(nums,start,end,pivot)\n",
    "            #print(nums[start:end])\n",
    "            #print(less,lessOrEqual,lessSum,largerSum)\n",
    "            if k<=less:\n",
    "                #k比当前值小，则需要将所有的大值都变为pivot，然后将pivot\n",
    "                ans=largerSum      #全部更大的值都需要变为pivot\n",
    "                kthValue,cost=serachKth(nums,start,start+less,k)    #假设start:less已经全部变了\n",
    "                #将[start+less:end]的pivot值全部变为kthvalue\n",
    "                ans+=cost+(pivot-kthValue)*(end-start-less)\n",
    "                return kthValue,ans\n",
    "            elif less<k<=lessOrEqual:      \n",
    "                #第k个值就是pivot，则其成本是固定的\n",
    "                ans=lessSum+largerSum\n",
    "                return pivot,ans\n",
    "            else:   \n",
    "                #第k个值在大于的区间中\n",
    "                #\n",
    "                ans=lessSum\n",
    "                kthValue,cost=serachKth(nums,start+lessOrEqual,end,k-lessOrEqual)\n",
    "                ans+=cost+(kthValue-pivot)*lessOrEqual\n",
    "                return kthValue,ans\n",
    "        #注意kth是第k个\n",
    "        return serachKth(nums,0,len(nums),(len(nums)>>1)+1)[1]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "    def minMoves2(self, nums: List[int]) -> int:\r\n",
    "        def partition(nums, l, r):\r\n",
    "            pivot = nums[r]\r\n",
    "            i = l - 1\r\n",
    "            for j in range(l, r):\r\n",
    "                if nums[j] < pivot:\r\n",
    "                    i+=1\r\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\r\n",
    "            nums[i+1], nums[r] = nums[r], nums[i+1]\r\n",
    "            return i+1\r\n",
    "        \r\n",
    "    \r\n",
    "        def randomPartition(nums, l, r):\r\n",
    "            index = random.randint(l, r)\r\n",
    "            nums[r], nums[index] = nums[index], nums[r]\r\n",
    "            return partition(nums, l, r)\r\n",
    "        \r\n",
    "        def fastMid(nums, l, r, k):\r\n",
    "            index = randomPartition(nums, l, r)\r\n",
    "            if index == k:\r\n",
    "                return nums[k]\r\n",
    "            if index < k:\r\n",
    "                return fastMid(nums, index+1, r, k)\r\n",
    "            else:\r\n",
    "                return fastMid(nums, l, index-1, k)\r\n",
    "            \r\n",
    "        fast_mid = fastMid(nums, 0, len(nums) - 1, len(nums)//2)\r\n",
    "            \r\n",
    "        return sum(abs(num - fast_mid) for num in nums)\r\n",
    "    \r\n",
    "        # nums.sort()\r\n",
    "        # return sum(abs(num - nums[len(nums) // 2]) for num in nums)\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "\r\n",
    "    \r\n",
    "    def minMoves2(self, nums: List[int]) -> int:\r\n",
    "        def partition(nums, l, r):\r\n",
    "            pivot = nums[r]\r\n",
    "            i = l - 1\r\n",
    "            for j in range(l, r):\r\n",
    "                if nums[j] < pivot:\r\n",
    "                    i+=1\r\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\r\n",
    "            nums[i+1], nums[r] = nums[r], nums[i+1]\r\n",
    "            return i+1\r\n",
    "        \r\n",
    "    \r\n",
    "        def randomPartition(nums, l, r):\r\n",
    "            index = random.randint(l, r)\r\n",
    "            nums[r], nums[index] = nums[index], nums[r]\r\n",
    "            return partition(nums, l, r)\r\n",
    "        \r\n",
    "        def fastMid(nums, l, r, k):\r\n",
    "            index = randomPartition(nums, l, r)\r\n",
    "            if index == k:\r\n",
    "                return nums[k]\r\n",
    "            if index < k:\r\n",
    "                return fastMid(nums, index+1, r, k)\r\n",
    "            else:\r\n",
    "                return fastMid(nums, l, index-1, k)\r\n",
    "            \r\n",
    "        fast_mid = fastMid(nums, 0, len(nums) - 1, len(nums)//2)\r\n",
    "        \r\n",
    "        result = 0\r\n",
    "        for item in nums:\r\n",
    "            result += abs(item - fast_mid)\r\n",
    "            \r\n",
    "            \r\n",
    "        return result\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        # 中位数贪心\n",
    "        # 快选找中位数\n",
    "        n = len(nums)\n",
    "        def partition(nums, l, r):\n",
    "            idx = randint(l, r)\n",
    "            nums[idx], nums[l] = nums[l], nums[idx]\n",
    "            pivot = nums[l]\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= pivot: \n",
    "                    r -= 1\n",
    "                nums[l] = nums[r]\n",
    "                while l < r and nums[l] < pivot: \n",
    "                    l += 1\n",
    "                nums[r] = nums[l]\n",
    "            nums[l] = pivot\n",
    "            return l\n",
    "        k = n // 2 + 1\n",
    "        def dfs(l, r):\n",
    "            p = partition(nums, l, r)\n",
    "            if p == k - 1:\n",
    "                return nums[p]\n",
    "            if p < k - 1:\n",
    "                return dfs(p+1, r)\n",
    "            return dfs(l, p-1)\n",
    "        \n",
    "        mid = dfs(0, n-1)\n",
    "        return sum(abs(mid - num) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        # 中位数贪心\n",
    "        # 快选找中位数\n",
    "        n = len(nums)\n",
    "        def partition(nums, l, r):\n",
    "            print(l, r)\n",
    "            idx = randint(l, r)\n",
    "            nums[idx], nums[l] = nums[l], nums[idx]\n",
    "            pivot = nums[l]\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= pivot: \n",
    "                    r -= 1\n",
    "                nums[l] = nums[r]\n",
    "                while l < r and nums[l] < pivot: \n",
    "                    l += 1\n",
    "                nums[r] = nums[l]\n",
    "            nums[l] = pivot\n",
    "            return l\n",
    "        k = n // 2 + 1\n",
    "        def dfs(l, r):\n",
    "            p = partition(nums, l, r)\n",
    "            if p == k - 1:\n",
    "                return nums[p]\n",
    "            if p < k - 1:\n",
    "                return dfs(p+1, r)\n",
    "            return dfs(l, p-1)\n",
    "        \n",
    "        mid = dfs(0, n-1)\n",
    "        return sum(abs(mid - num) for num in nums)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
